/** 冒泡排序
 * 时间复杂度：O(n平方)
 * 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置。否则，位置不变
*/

/** 冒泡排序的最原始版本 */
function sort(arr) {
    for (let i = 0;i < arr.length - 1;i++) {
        for(let j = 0;j<arr.length - i - 1;j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

// console.info(sort([44,23,12,99,234]))

/** 优化1
 * 给一个参数做标记，记录在每一次循环的过程中，是否有交换，如果没有交换，说明剩下的循环就是满足顺序的。就可以直接跳出剩下的循环
 */

function sort1(arr) {
    for (let i = 0;i < arr.length - 1;i++) {
        let isSorted = true; // 有序标记，每一轮的初始值都是true
        for(let j = 0;j<arr.length - i - 1;j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false; // 因为有元素进行交换，所以不是有序的，标记为false
            }
        }
        if (isSorted) {
            break;
        }
    }
    return arr
}

// console.info(sort1([5,8,1,2,3]))

/** 优化2
 * 我们再看下另外一个例子[3,4,2,1,5,6,7,8],其实后面已经是排序好的了。所以不需要再继续排序了。那么在优化1的基础上，再记录下，排序最后的位置，也就是说。位置的左边需要排序，右边是排序好的
 */

 function sort2(arr) {
    let sortBorder = arr.length - 1; // 这里的最后位置已经改变了，j不再从i中取。
    let lastExchangeIndex = 0; // 最后一个交换的位置，是给sortBorder赋值用的
    for (let i = 0;i < arr.length - 1;i++) {
        let isSorted = true; // 有序标记，每一轮的初始值都是true
        for(let j = 0;j<sortBorder;j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false; // 因为有元素进行交换，所以不是有序的，标记为false
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        console.info(sortBorder, isSorted, arr)
        if (isSorted) {
            break;
        }
    }
    return arr
}

console.info(sort2([3,4,2,1,5,6,7,8]))
